class MountainArray(object):
    def get(self, index):
        """
        :type index: int
        :rtype int
        """

    def length(self):
        """
        :rtype int
        """


class Solution(object):
    def findInMountainArray(self, target, mountain_arr):
        n = len(mountain_arr)
        left_index = 0
        right_index = n - 1
        left_val = mountain_arr.get(left_index)
        right_val = mountain_arr.get(right_index)

        def find(left_index, right_index, left_val, right_val):
            if target == left_val:
                return left_index
            if right_index - left_index <= 1:
                if target == right_val:
                    return right_index
                else:
                    return -1
            mid_index = (left_index + right_index) // 2
            mid_val = mountain_arr.get(mid_index)
            if left_val < mid_val:
                if mid_val <= right_val:
                    if target < left_val:
                        return -1
                    if target == left_val:
                        return left_index
                    if left_val < target < mid_val:
                        return find(left_index, mid_index, left_val, mid_val)
                    if target == mid_val:
                        return mid_index
                    return find(mid_index, right_index, mid_val, right_val)
                else:
                    if target == left_val:
                        return left_index
                    if target > left_val:
                        index = find(left_index, mid_index, left_val, right_val)
                        if index >= 0:
                            return index
                    if target >= right_val:
                        return find(mid_index,right_index, mid_val,right_val)
                    return -1
            else:
                if left_val == mid_val:
                    if target > left_val:
                        return find(left_index, mid_index, left_val, mid_val)
                    if target >= right_val:
                        return find(mid_index, right_index, mid_val, right_val)
                    else:
                        return -1
                else:
                    if target > mid_val:
                        return find(left_index, mid_index, left_val, right_val)
                    if target == mid_val:
                        return mid_index
                    if right_val < target < mid_val:
                        return find(mid_index, right_index, mid_val, right_val)
                    if target == right_val:
                        return right_index
                    return -1
        return find(left_index, right_index, left_val, right_val)
